import java.io.*;
import java.util.*;
import java.lang.Float;
import java.math.*;

class Anderson {
	public static Stack<Float> P;
	public static Stack<Float> N;
	public static Stack<Float> E;
	public static Stack<Float> inputStack;
	public static int flops;

	public static  class ReducedNumber {
		ReducedNumber(float t, float u) {
			this.u = u;
			this.t = t;	
		}
		float t;
		float u;
	}

	public static class DeflatedNumber {
		float s;
		float e;
	}

	public static void main(String args[]) {
		N = new Stack<Float>();
		P = new Stack<Float>();
		E = new Stack<Float>();
		flops = 0;
		inputStack = new Stack<Float>();
		int reductionCounter = 0;
		float R = 0;
		long loadStart = System.currentTimeMillis();
		loadNumbersFromAFile();
		long loadEnd = System.currentTimeMillis();	
		System.out.println("time to load data " + (loadEnd - loadStart));	

		fillBucketsWithNumbers();
		long runStart = System.currentTimeMillis();
		float lastR = 0;
		while(R != 1) {
			// deflate until one set is empty
			while(P.size() > 0 && N.size() > 0) {
				removeAndDeflateARow();
			}
			// redistribute E into P and N
			while(E.size() > 0) {
				float temp = E.pop().floatValue();
				if(temp > 0) {
					P.push(new Float(temp));
				}
				else {
					N.push(new Float(temp));
				}
			}
			R = calculateR();
			if(R == lastR) {
				reductionCounter++;
				reduceN();
				reduceP();
			}
			lastR = R;
	 	}
		float sum = compensatedSumP() + compensatedSumN();
		long runEnd = System.currentTimeMillis();
		System.out.println("time to run " + (runEnd - runStart));
		System.out.println(new BigDecimal(sum));
		System.out.println("number of reductions " + reductionCounter);
		System.out.println("flops " + flops);
	}
	
	static void reduceN() {
		Float temp = (Float) N.remove(0);
		ReducedNumber reducedNumber = reduce(temp);
			N.push(reducedNumber.t);
			N.push(reducedNumber.u);
	}	

	static void reduceP() {
		float temp = P.remove(0);		
		ReducedNumber reducedNumber = reduce(temp);
			P.push(reducedNumber.t);
			P.push(reducedNumber.u);
	}
	
	static float calculateR() {
		float Splus = compensatedSumP();
		float Sminus = compensatedSumN();
		float R = Math.abs((Splus + Sminus) / (Splus - Sminus));
		if(Float.isNaN(R)) {
			R = 1;
		}
		return R; 
	}
 
	static float compensatedSumP() {
		if(P.size() == 0)
			return 0;
		float c = 0;
		float sum = 0;
		sum = P.elementAt(0);
		float y = 0;
		float t = 0;
		// add everything in P
		int n = P.size();
		for(int i = 1; i < n; i++) {
			flops += 4;
			y = P.elementAt(i) - c;
			t = sum + y;
			c = (t - sum) - y;
			sum = t;
		}
		return sum;
	}

	static float compensatedSumN() {
		if(N.size() == 0)
			return 0;
		float c = 0;
		float sum = 0;
		sum = N.elementAt(0);
		float y = 0;
		float t = 0;
		// add everything in N
		int n = N.size();
		for(int i = 1; i < n; i++) {
			flops += 4;
			y = N.elementAt(i) - c;
			t = sum + y;
			c = (t - sum) - y;
			sum = t;
		}
		return sum;
	}

	static DeflatedNumber deflate(float a, float b) {
		float s;
		float e;
		flops += 3;
		// ensure that a is always positive and b 
		// is always negative
		if(a < b) {
			float temp = a;
			a = b;
			b = temp;
		}		
		s = a + b;
		// if abs(a) > abs(b)
		if(s > 0) {
			e = a - s;
			e = e + b;
		}
		else {
			e = b - s;
			e = e + a;
		}
		DeflatedNumber deflatedNumber = new DeflatedNumber();
		deflatedNumber.s = s;
		deflatedNumber.e = e;
		return deflatedNumber;
	}

	static ReducedNumber reduce(float a) {
		float t;
		float u = 0;
		t = a;
		while((a-t) != a) {
			flops += 2;
			u = t;
			t = t / 2;
		}
		flops++;
		t = a - u;
		return new ReducedNumber(t, u);
	}
	
	static ReducedNumber reduce2(float a) {
		float t = (float) Math.sqrt((double)a);
		float u = a - t;
		return new ReducedNumber(t,u);
	}

	static void removeAndDeflateARow() {
		float s;
		float e;
		float a = P.pop().floatValue();
		float b = N.pop().floatValue();

		DeflatedNumber deflatedNumber = deflate(a, b);
		if(deflatedNumber.s == deflatedNumber.e) {
			ReducedNumber reducedNumber = reduce(a);
			if(reducedNumber.t >= 0)
				P.push(new Float(reducedNumber.t));
			else 
				N.push(new Float(reducedNumber.t));
			if(reducedNumber.u >= 0)
				P.push(new Float(reducedNumber.u));
			else
				N.push(new Float(reducedNumber.u));	
		}
		else {
			if(deflatedNumber.e > 0) 
				E.push(new Float(deflatedNumber.e));
			if(deflatedNumber.s >= 0)
				P.push(new Float(deflatedNumber.s));
			else 
				N.push(new Float(deflatedNumber.s));
		}
 	}		

	public static void fillBucketsWithNumbers() {
		float number;
		while(inputStack.size() > 0) {
			number = ((Float) inputStack.pop()).floatValue();
			if(number > 0) {
				P.push(number);
			}
			if(number < 0) {
				N.push(number);
			}
		}
	}
	
	public static void loadNumbersFromAFile() {
		try {
			Scanner sc = new Scanner(new File("numbers"));
			while(sc.hasNextFloat()) {
				float temp = sc.nextFloat();
					inputStack.push(temp);
			}		
		}
		catch(FileNotFoundException e) {

		}	
	}
}
